/**
 * 亚马逊面试题目
 *
 * 寻找一个字符串中，每个字符之后比自己大的字符的个数，字符为大写字母、小写字母混合
 *
 * 解题思路： 利用归并排序稳定性的特点，计算交换次数来，来统计大的字符个数
 */
function merge(left,right, staticMap){
    let result = [];
    while (left.length > 0 && right.length > 0){
        if(left[0] < right[0]){
            result.push(left.shift());
        }else{
            staticMap.set(left[0], staticMap.get(left[0]) + 1);
            result.push(right.shift());
        }
    }
    while (left.length) result.push(left.shift());
    while (right.length) result.push(right.shift());
    return result;
}

function mergeSort(arr, staticMap){
    let len = arr.length;
    if(len < 2) return arr;
    let mid = Math.floor(len / 2);
    let left = arr.slice(0,mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left, staticMap),mergeSort(right, staticMap),staticMap);
}

function staticCount(arr){
    const staticMap  = new Map();
    arr.forEach(item => {
        staticMap.set(item, 0);
    });
    mergeSort(arr,staticMap);
    let len = arr.length - 1;
    arr.forEach((item,index) => {
        staticMap.set(item, len - index - staticMap.get(item))
    })
    return staticMap;
}

/**
 * 亚马逊面试题
 *
 * 单词接龙，输出所有单词的路径
 */
class Solution {
    constructor() {
        this.wordId = new Map();
        this.edge = new Array();
        this.nodeNum = 0;
        this.path = new Map();
    }

    addWord(word){
        if(!this.wordId.has(word)){
            this.wordId.set(word,this.nodeNum++);
            this.edge.push(new Array());
        }
    }

    addEdge(word){
        this.addWord(word);
        let id1 = this.wordId.get(word);
        let array = Array.from(word);
        let length = array.length;
        for(let i=0; i < length; ++i){
            let tmp = array[i];
            array[i] = '*';
            let newWord = array.join('');
            this.addWord(newWord);
            let id2 = this.wordId.get(newWord);
            this.edge[id1].push(id2);
            this.edge[id2].push(id1);
            array[i] = tmp;
        }
    }
    ladderLength(beginWord, endWord, wordList){
        wordList.forEach((word) => this.addEdge(word));
        this.addEdge(beginWord);
        if(!this.wordId.has(endWord)){
            return 0;
        }
        let dis = new Array(this.nodeNum);
        dis.fill(Number.MAX_SAFE_INTEGER);
        let beginId = this.wordId.get(beginWord), endId = this.wordId.get(endWord);
        dis[beginId] = 0;
        let queue = new Array();
        queue.push(beginId);
        while (queue.length){
            let x = queue.shift();
            if(x === endId){
                console.log(this.wordId);
                console.log(this.path);
                return dis[endId] / 2 + 1;
            }
            this.edge[x].forEach(item => {
                if(dis[item] === Number.MAX_SAFE_INTEGER){
                    dis[item] = dis[x] + 1;
                    queue.push(item);
                    this.path.set(item, x);
                }
            });
        }
        return 0;
    }
}
// const s = new Solution();
// console.log(s.ladderLength("hit","cog", ["hot","dot","dog","lot","log","cog"]));

/**
 * 亚马逊面试题 找零钱问题
 *
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 *
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 */
const change = function(amount, coins){
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for(const coin of coins){
        for(let i = coin; i<=amount; i++){
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}
